package nowcoderLinkList;

public class MySingleList2 {
    //定义节点
    class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public MySingleList.ListNode head;

    //11 链表相加
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //1.两个链表有一个为空，则返会另一个链表
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        //都不为空的情况下  先反转两个链表
        head1 = reverseList2(head1);
        head2 = reverseList2(head2);
        // 设置两个链表的表头  设置carry进制
        ListNode res = new ListNode(-1);
        ListNode head = res;
        int carry = 0;
        //遍历两个链表   直到两个链表为空，carry=0
        while (head1 != null || head2 != null || carry != 0) {
            int val1 = head1 == null ? 0 : head1.val;
            int val2 = head2 == null ? 0 : head2.val;
            int temp = val1 + val2 + carry;
            carry = temp / 10;  //获取进位
            temp %= 10;//每个位上的数字是temp
            head.next = new ListNode(temp);//添加位上的数字
            //一起往后移动
            head = head.next;
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }
        //新链表（得到的结果）反转回来
        return reverseList2(res.next);
    }

    //12  单链表的排序

    //合并两个有序的链表
    public ListNode merge(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
        if (pHead1 == null) cur.next = pHead2;
        if (pHead2 == null) cur.next = pHead1;
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //走完了，这个mid也就在中间了  此时断开就可以了
        left.next = null;
        return merge(sortInList(head),sortInList(mid));
    }

    //13 判断一个链表是否为回文结构
    public MySingleList.ListNode reverse(MySingleList.ListNode head) {
        if (head == null ||head.next == null) return head;
        MySingleList.ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            MySingleList.ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    public boolean isPail (MySingleList.ListNode head) {
        // write code here
        if (head == null || head.next == null)  return true;
        MySingleList.ListNode slow = head;
        MySingleList.ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverse(slow);
        fast = head;
        while (slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    //14 链表的奇偶重排
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode head1 = new ListNode(-1);

        ListNode left = head;
        ListNode right = head.next;

        head1 = left;
        ListNode head2 = right;

        ListNode cur1 = left;
        ListNode cur2 = right;
        while (right != null && right.next != null) {
            left = left.next.next;
            cur1.next = left;
            cur1 = cur1.next;
            right = right.next.next;
            cur2.next = right;
            cur2 = cur2.next;
        }
        cur1.next = head2;
        return head1;
    }
    //15 删除链表中的重复元素-I
    public MySingleList.ListNode deleteDuplicates1 (MySingleList.ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        MySingleList.ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
    //16 删除有序链表中重复的元素-II
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int tmp = cur.next.val;
                while (cur.next != null && tmp == cur.next.val) {
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return res.next;
    }

    //17 二分查找-I   二分查找的数组一定是有序的
    public int search (int[] nums, int target) {
        // write code here
        int left = 0;
        int right = nums.length-1;
        for (int i = 0; i < nums.length; i++) {
            while (left <= right) {
                //mid要写到这里，因为每次中间下标都是改变的，L和R变才会使M下标变
                int mid = (left+right) / 2;
                if (target < nums[mid]) {
                    right = mid - 1;
                }else if (target > nums[mid]) {
                    left = mid + 1;
                }else {
                    return mid;
                }
            }
        }
        return -1;//这里就是循环走完了，就是没找到
    }

    //18 二维数组中的查找
    public boolean Find2(int target, int [][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (target == array[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean Find(int target, int [][] array) {
        //判断特殊
        if (array.length == 0 || array[0].length == 0) return false;
        int n = array.length;
        int m = array[0].length;
        //从最左下角的元素往上找
        for (int i = n - 1,j = 0; i >= 0 && j < m;) {
            if (array[i][j] > target) {//target较小，就往上找
                i--;
            }else if (array[i][j] < target) {//target较大， 就往右找
                j++;
            }else {
                return true;
            }
        }
        return false;
    }

    //19 寻找峰值
    public int findPeakElement (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid+1]) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }

    /*//20 数组中的逆序对
    public int mergeSort(int[] array,int left,int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,right,mid);
    }
    public int merge(int[] array,int left,int right,int mid) {

    }
    public int InversePairs(int [] array) {

    }*/

    //21 旋转数组的最小数字
    public int minNumberInRotateArray1(int [] array) {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
    public int minNumberInRotateArray(int [] array) {
        int l = 0;
        int r = array.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (array[m] > array[r]) {
                l = m + 1;
            }else if (array[m] < array[r]) {
                r = m;
            }else {
                r--;
            }
        }
        return array[l];
    }
}
